--[[
    选择排序
    可做优化的点的
        1. 时间复杂度O(n^2)
        2. 性能上优于冒泡排序

    node = {
        id 作为大小比较值
    }
--]]


require("dump")

local table_insert = table.insert
local table_remove = table.remove

local SSort = {}

function SSort.new(...)
    local instance = setmetatable({}, {__index=SSort})
    instance:ctor(...)
    return instance
end

function SSort:ctor()
    self.nodes = {} --用于存放数据
end

--
function SSort:push(node)
    table_insert(self.nodes, node)
    return
end

--优先取id值大的node
function SSort:pop()
    if not self.nodes or not self.nodes[1] then
        return
    end
    local value = self.nodes[1]
    table_remove(self.nodes, 1)
    return value
end

function SSort:getTop()
    return self.nodes[1]
end

function SSort:getNodes()
    return self.nodes
end

function SSort:print()
    for i = 1, #self.nodes do
        print(i, self.nodes[i].id)
    end
end

function SSort:size()
    return #self.nodes
end

function SSort:sort()
    local i = 1
    local j = 1
    local min = 1
    local len = self:size()
    print("___len:", len)
    for i=1, len do
        min = i
        for j=i+1, len do
            if self.nodes[min].id > self.nodes[j].id then
                min = j
            end
        end
        if min ~= i then
            --交换
            local tmp = self.nodes[i]
            self.nodes[i] = self.nodes[min]
            self.nodes[min] = tmp
        end
    end
end

------------------------------------------------------------------
--测试
------------------------------------------------------------------
if arg and arg[0] == "ssort.lua" then
    local ssort = SSort.new()
    ssort:push({id=2})
    ssort:push({id=12})
    ssort:push({id=1})
    ssort:push({id=8})
    ssort:push({id=6})
    ssort:push({id=5})
    ssort:push({id=6})
    ssort:push({id=16})
    ssort:push({id=26})
    ssort:print()
    print("_______")
    ssort:sort()
    ssort:print()
    print("_______")

    print("____min:", tostring(ssort:pop()))
    --print("____min:", tostring(SSort:pop()))
end

return SSort